// return the first ans in [lo, hi], such as check(md) = true
// if no such ans, return hi + 1
template<class T, class Func>
T binary_min_left(T lo, T hi, Func check) {
	T ans = hi + 1;
	while(lo <= hi) {
		T md = lo + (hi - lo) >> 1;
		if(check(md)) {
			ans = md;
			hi = md - 1;
		} else {
			lo = md + 1;
		}
	}
	return ans;
}


// return the last ans in [lo, hi], such as check(md) = true
// if no such ans, return lo - 1
template<class T, class Func>
T binary_max_right(T lo, T hi, Func check) {
	T ans = lo - 1;
	while(lo <= hi) {
		T md = lo + (hi - lo) >> 1;
		if(check(md)) {
			ans = md;
			lo = md + 1;
		} else {
			hi = md - 1;
		}
	}
	return ans;
}